/*
题目: 和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
 */
public class ShortestSubarray {
    public int shortestSubarray(int[] nums, int k) {
        // 前缀和 + 单调队列
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i ++)
            prefix[i + 1] = prefix[i] + nums[i];

        Deque<Integer> deque = new LinkedList<> ();
        int minn = Integer.MAX_VALUE;
        // 此处 需要从 0 开始遍历, 处理 prefix[最后一个下标] >= k, 也就是数组总和的情况
        for (int i = 0; i <= n; i ++) {
            //       |
            //    |  |  |
            // |  |  |  |
            // 0  1  2  3  排除掉高的, 后面即使出现 prefix[i] - prefix[2] >= k 的, 也必然出现 prefix[i] - prefix[3] >= k
            while (!deque.isEmpty() && prefix[deque.peekLast()] >= prefix[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 从前面找到满足的直接弹出，因为如果后面即便出现满足条件的，使得preSum[cur]-preSum[开头] >= k ,
            // 则其长度也比当前的（当前下标-开头）长（当前是满足的），所以开头的满足条件的已经没有存在的意义了
            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {
                // 前缀和 两个坐标相减 得到的就是  实际中子数组 的长度
                minn = Math.min(minn, i - (int) deque.pollFirst());
            }
        }

        return minn == Integer.MAX_VALUE ? -1 : minn;
    }
}
